/**
 * 
 */
package leetCode;

/**
 * 给定n和k，求1-n数列组成的序列，并且满足相邻差绝对值的个数为k
 * 
 * @author zhongfang
 *
 */
public class BeautifulArrangementII {
	boolean success = false;
	int kk = 0;
	int nn;
	int diff[];
	int cnt=0;//不同个数
	public int[] constructArray(int n, int k) {
		int a[] = new int[n];
		for (int i = 0; i < a.length; i++) {
			a[i]=i+1;
		}
		kk = k;
		nn=n;
		diff=new int[100010];
		help(a,0, n);
		return a;
	}

	private void help(int[] a,int left, int right) {
		int record = -1;
		int tmp;
		if (success) {
			return;
		}
		if (right == 0) {
			if(cnt==kk){
				success=true;
			}
			return;
		}
		if(right+cnt<kk){//回溯
			return;
		}
		
		for (int i= left; i < right; i++) {
			swap(0,i,a);
			if(right!=nn){//还没有到最后一个
				tmp=Math.abs(a[0]-a[-1]);
				if(diff[tmp]==0){
					diff[tmp]=1;
					cnt++;
					record=tmp;
				}
			}
			help(a,left+1, right-1);//递归
			if(record>0){
				diff[record]=0;
				cnt--;
				record=-1;
			}
			swap(i, 0, a);
		}
	}

	private void swap(int i, int j, int[] a) {
		int tmp=a[i];
		a[i]=a[j];
		a[j]=tmp;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
	}

}
